// https://www.lintcode.com/problem/binary-tree-level-sum/my-submissions?_from=ladder&&fromId=86

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
// 法一：BFS，层序遍历（写了好多次，很容易出错）
// class Solution {
// public:
//     /**
//      * @param root: the root of the binary tree
//      * @param level: the depth of the target level
//      * @return: An integer
//      */
 
//     int levelSum(TreeNode * root, int level) {
//         queue<TreeNode *> q;
//         if (!root) return 0;
//         q.push(root);
//         int s = 0;
//         int l = 0;
//         int result = 0;
//         vector<vector<int>> traverse_result;
//         while (!q.empty())
//         {
//             s = q.size();
//             vector<int> t;
//             if (l == level) break;
//             for (int i = 0; i < s; ++i)
//             {
//                 TreeNode *tmp = q.front();
//                 t.push_back(tmp->val);
//                 q.pop();
//                 if (tmp->left) q.push(tmp->left);
//                 if (tmp->right) q.push(tmp->right);
//             }
//             traverse_result.push_back(t);
//             l++;
//         }
//         for (auto t: traverse_result)
//         {
//             for (auto tt: t)
//                 cout << tt << " " << endl;
//         }
//         if (level > l || level < 1) return 0;
//         for (int i = 0; i < traverse_result[l - 1].size(); ++i)
//         {
//             result += traverse_result[l - 1][i];
//         }
//         return result;
//     }

class Solution {
public:
    int levelSum(TreeNode * root, int level) {
        int sum = 0;
        dfs(root, 1, level, sum);
        return sum;
    }
    void dfs(TreeNode * root, int tmp, int level, int& sum)
    {
        if (!root) return;
        if (tmp == level) {sum += root->val;}
        dfs(root->left, tmp + 1, level, sum);
        dfs(root->right, tmp + 1, level, sum);
    }
};